/*
 * Copyright (c) 2008, Justin Choy
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 * 
 * 1) Redistributions of source code must retain the above copyright notice, 
 * this list of conditions and the following disclaimer.
 * 
 * 2) Redistributions in binary form must reproduce the above copyright notice, 
 * this list of conditions and the following disclaimer in the documentation 
 * and/or other materials provided with the distribution.
 * 
 * 3) Neither the name of the owner nor the names of its contributors may 
 * be used to endorse or promote products derived from this software without 
 * specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
 * POSSIBILITY OF SUCH DAMAGE.
 */
package algorithms;

import data.Array;
import error.OutOfMemoryException;
import error.ProgrammingErrorException;

/**
 * An example of using the Merge sort Algorithm
 * The merge sort merges two sorted arrays into 1 bigger sorted array. It uses
 * recursion to break down an array until it gets to the base case of a 1 
 * element array (which is sorted) and merges two 1 element arrays together.
 * 
 * O(NlogN)
 * 
 * @author jchoy
 */
public class MergeSort {
    public MergeSort() {
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        try {
            MergeSort.MergeSortedArray array 
                = new MergeSort().new MergeSortedArray();
            
            System.out.println( "Filling Array...");
            array.fillWithRandomNumbers(50000);
            
            System.out.println( "Merge Sorting..." );
            
            long startTime = System.currentTimeMillis();
            array.sort();
            long stopTime = System.currentTimeMillis();
            long sortTime = stopTime - startTime;
            
            System.out.println( "It took " + Long.toString(sortTime) + "ms");
            
            System.out.print( "Testing sort...");
            
            if ( array.isOrdered() == true) {
                System.out.println( "PASS!" );
            } else {
                System.out.println( "FAIL!" );
            }
            
        } catch (ProgrammingErrorException e) {
            System.out.println( e.getMessage() );
        } catch (OutOfMemoryException e) {
            System.out.println(e.getMessage());
        }
    }
    
    
    class MergeSortedArray extends Array {
        public MergeSortedArray() {
        }
        
        /**
         * Sorts the array using merge sort.
         * 
         * @throws ProgrammingErrorException 
         */
        public void sort() throws ProgrammingErrorException {
            long[] tempArray = new long[getNumElements()];
            mergeSort(0, getNumElements() - 1, tempArray);
        }
        
        /**
         * Sorts this.array between the passed in start and stop indexes.
         * This method splits the array in two and sorts the two halves and
         * merges the two sorted halves together.
         * 
         * @param start The index where we should start sorting from
         * @param stop The index where we should stop sorting
         * @param tempArray A temporary storage array that must have at least
         * enough space to hold all the elements between and inclusive
         * of start and stop.
         */
        private void mergeSort( int start, int stop, long[] tempArray) {
            
            /* If we only have less than 2 elements then its already sorted */
            if ( stop <= start ) {
                ; /* No Op */
                
            } else {
                int mid = ( start + stop ) >>> 1;
                
                mergeSort( start, mid, tempArray );
                mergeSort( mid + 1, stop, tempArray );
                
                mergeSortedArrays( start, mid + 1, stop, tempArray);
            }
        }
        
        /**
         * Merges two sorted halves of the this.array into one sorted array.
         * 
         * @param lowerStart The index of the starting point of the lower half
         * @param upperStart The index of the starting point of the upper half.
         * This index should be one past the stop point of the lower half
         * @param stop The index of the stopping point of the upper half
         * @param tempArray A temporary storage array that must have at least
         * enough space to hold all the elements between and inclusive of
         * start and stop.
         */
        private void mergeSortedArrays( int lowerStart, int upperStart,
                int stop, long[] tempArray ) {
            
            int lowerStop = upperStart - 1;
            int lowStart = lowerStart;
            int numItems = stop - lowerStart + 1;
            int i = 0;
            
            /* Start merging the two until one is finished */
            while ( (lowerStart <= lowerStop) && (upperStart <= stop) ) {
                if ( array[lowerStart] < array[upperStart] ) {
                    tempArray[i++] = array[lowerStart++];
                } else {
                    tempArray[i++] = array[upperStart++];
                }
            }
            
            /* Finish filling with whichever one is not done */
            while ( lowerStart <= lowerStop) {
                tempArray[i++] = array[lowerStart++];
            }
            
            /* Finish filling with whichever one is not done */
            while ( upperStart <= stop ) {
                tempArray[i++] = array[upperStart++];
            }
            
            /* Copy the values back to the source array */
            for ( i = 0; i < numItems; i++ ) {
                array[lowStart + i] = tempArray[i];
            }
            
        }
    }
    
    

}
